]> dgit.raspbian.org Git - dovecot.git/commit
[PATCH 3/3] lib-storage: thread - Limit ancestor chain traversal depth to prevent...
authorTimo Sirainen <timo.sirainen@open-xchange.com>
Fri, 17 Apr 2026 13:15:54 +0000 (13:15 +0000)
committerNoah Meyerhans <noahm@debian.org>
Wed, 16 Sep 2026 19:06:35 +0000 (15:06 -0400)
commitb1f9c0b05dbee0cfda03730d1dc532023f407a55
treef5c28426458730e556309981a6b597da6b6a1d9f
parent1a7e39480245e75587e85b02c083f83275cc9929
[PATCH 3/3] lib-storage: thread - Limit ancestor chain traversal depth to prevent O(N^2) CPU usage

The per-message References limit (MAIL_THREAD_REFERENCES_MAX) prevents a
single crafted message from causing O(N^2) traversals in
thread_node_has_ancestor(). However, multiple crafted messages each
containing 1000 References entries can build an arbitrarily deep ancestor
chain across the mailbox, causing the same quadratic blowup spread over
many messages: processing email k costs O(k * MAIL_THREAD_REFERENCES_MAX)
steps, giving O(M^2 * MAIL_THREAD_REFERENCES_MAX) total for M emails.

Fix this by limiting the traversal depth in thread_node_has_ancestor() to
MAIL_THREAD_REFERENCES_MAX steps. When the limit is reached the link is
dropped, bounding per-email work to O(MAIL_THREAD_REFERENCES_MAX^2)
regardless of how deep the chain was built by prior messages.

Gbp-Pq: Name 0003-lib-storage-thread-Limit-ancestor-chain-traversal-de.patch
src/lib-storage/index/index-thread-links.c